import java.util.Deque;
import java.util.LinkedList;

public class Leetcode2331 {
    public boolean evaluateTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (root.left == null && root.right == null) {
            return root.val == 1;
        }

        return root.val == 2 ? evaluateTree(root.left) || evaluateTree(root.right) : evaluateTree(root.left) && evaluateTree(root.right);
    }

    public static boolean evaluateTree1(TreeNode root) {
        boolean res = true;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if (root.right == null || root.right == prev) {
                prev = root;
                root = null;
            } else {
                if (root.val == 2) {
                    res = root.left.val == 1 || root.right.val == 1;
                }else{
                    res = root.left.val == 1 && root.right.val == 1;
                }

                stack.push(root);
                root = root.right;
            }
        }

        return res;
    }
}
